#include <bits/stdc++.h>

using namespace std;
#define int long long
const int inf = 0x3f3f3f3f;

void solve()
{
	int a, b;
	cin >> a >> b;
	int ans = inf;
	function<void(int, int, int)> dfs = [&](int a, int b, int ret)->void {
		if (a == 0 || b == 0)
		{
			ans = min(ans, ret + 1);
			return;
		}
		if (ret >= min(ans, 26LL)) return;
		int g = __gcd(a, b);
		dfs(a - g, b, ret + 1);
		dfs(a, b - g, ret + 1);
		};
	dfs(a, b, 0);
	cout << ans << endl;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--)
	{
		solve();
	}
	return 0;
}